#define  _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<vector>
#include<string>

using namespace std;

//class Solution
//{
//public:
//    vector<int> findSubstring(string s, vector<string>& words)
//    {
//        string s1 = words[0] + words[1];
//        string s2 = words[1] + words[0];
//        vector<int> v;
//        int len = s1.size();
//        int i = 0, j = i + len - 1, n = s.size();
//        while (i <= n - len)
//        {
//            string temp;
//            for (int left = i; left <= j; left++)
//            {
//                temp += s[left];
//            }
//            if (temp == s1 || temp == s2) v.push_back(i);
//            i++;
//            j++;
//        }
//        return v;
//    }
//};
//
//int main()
//{
//    string s("barfoothefoobarman");
//    vector<string> words;
//    words.push_back("foo");
//    words.push_back("bar");
//    vector<int> v = Solution().findSubstring(s, words);
//    for (auto& e : v)
//    {
//        cout << e << " ";
//    }
//    cout << endl;
//    return 0;
//}

//class Solution 
//{
//public:
//    bool exist(vector<string>& board, string word) 
//    {
//        int row = board.size();
//        int col = board[0].size();
//        vector<vector<int>> vv;
//        vv.reserve(row);
//        for(int i = 0;i < row;i++)
//        {
//            vv[i].reserve(col);
//        }
//        for(int i = 0;i < row;i++)
//        {
//            for(int j = 0;j < col;j++)
//                cout << vv[i][j] << " ";
//            cout << endl;
//        }
//        return true;
//    }
//};
//
//int main()
//{
//    int row = 3;
//    int col = 4;
//    vector<vector<int>> vv;
//    vv.reserve(row);
//    for (int i = 0; i < row; i++)
//    {
//        vv[i].resize(col);
//    }
//    for (int i = 0; i < row; i++)
//    {
//        for (int j = 0; j < col; j++)
//            cout << vv[i][j] << " ";
//        cout << endl;
//    }
//    return 0;
//}

//class Solution
//{
//public:
//    string solve(string s, string t)
//    {
//        int lens = s.size();
//        int lent = t.size();
//        if (lens == 0) return t;
//        if (lent == 0) return s;
//        string ans;
//        ans.reserve(lens > lent ? lens + 1 : lent + 1);
//        int ends = lens - 1;
//        int endt = lent - 1;
//        int change = 0;
//        while (ends >= 0 || endt >= 0)
//        {
//            int vals = ends >= 0 ? s[ends--] - '0' : 0;
//            int valt = endt >= 0 ? s[endt--] - '0' : 0;
//            int sum = vals + valt + change;
//            if (sum >= 10)
//            {
//                change = 1;
//                sum -= 10;
//            }
//            else change = 0;
//            ans += (sum + '0');
//        }
//
//        if (change == 1) ans += '1';
//
//        reverse(ans.begin(), ans.end());
//
//        return ans;
//    }
//};

//struct ListNode 
//{
//    int val;
//    struct ListNode* next;
//
//    ListNode(int x) : val(x), next(nullptr) {}
//};
//
//class Solution
//{
//public:
//    ListNode* addInList(ListNode* head1, ListNode* head2)
//    {
//        ListNode* cur1 = head1;
//        ListNode* prev1 = nullptr;
//        while (cur1)
//        {
//            ListNode* next = cur1->next;
//            cur1->next = prev1;
//            prev1 = cur1;
//            cur1 = next;
//        }
//        cur1 = prev1;
//
//        ListNode* cur2 = head2;
//        ListNode* prev2 = nullptr;
//        while (cur2)
//        {
//            ListNode* next = cur2->next;
//            cur2->next = prev2;
//            prev2 = cur2;
//            cur2 = next;
//        }
//        cur2 = prev2;
//
//        ListNode* newhead = nullptr;
//        ListNode* tail = newhead;
//        int change = 0;
//        while (cur1 || cur2)
//        {
//            int val1 = cur1 == nullptr ? 0 : cur1->val;
//            int val2 = cur2 == nullptr ? 0 : cur2->val;
//            int sum = val1 + val2 + change;
//            if (sum >= 10)
//            {
//                change = 1;
//                sum -= 10;
//            }
//            else change = 0;
//            if (newhead == nullptr)
//            {
//                newhead = new ListNode(sum);
//                tail = newhead;
//            }
//            else
//            {
//                tail->next = new ListNode(sum);
//                tail = tail->next;
//            }
//            if(cur1)
//                cur1 = cur1->next;
//            if(cur2)
//                cur2 = cur2->next;
//        }
//        if (change == 1)
//        {
//            tail->next = new ListNode(1);
//            tail = tail->next;
//        }
//
//         ListNode* cur = newhead;
//         ListNode* prev = nullptr;
//         while(cur)
//         {
//             ListNode* next = cur->next;
//             cur->next = prev;
//             prev = cur;
//             cur = next;
//         }
//         cur = prev;
//
//        return cur;
//    }
//};
//
//int main()
//{
//    ListNode* head1 = new ListNode(9);
//    ListNode* tail1 = head1;
//    tail1->next = new ListNode(3);
//    tail1 = tail1->next;
//    tail1->next = new ListNode(7);
//    tail1 = tail1->next;
//
//    ListNode* head2 = new ListNode(6);
//    ListNode* tail2 = head2;
//    tail2->next = new ListNode(3);
//    tail2 = tail2->next;
//
//    Solution().addInList(head1, head2);
//    return 0;
//}

//class Solution
//{
//public:
//    int removeDuplicates(vector<int>& nums)
//    {
//        int cur = 0, dest = 0, n = nums.size();
//        while (cur < n)
//        {
//            if (nums[cur] != nums[dest])
//            {
//                dest++;
//                nums[dest] = nums[cur];
//            }
//            cur++;
//        }
//        return dest + 1;
//    }
//};
//
//class Solution
//{
//public:
//    vector<int> searchRange(vector<int>& nums, int target)
//    {
//        vector<int> v(2, -1);
//        if (nums.size() == 0) return v;
//        int left = 0, n = nums.size() - 1, right = n;
//        while (left < right)
//        {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] < target) left = mid + 1;
//            else if (nums[mid] >= target) right = mid;
//        }
//        if (nums[left] == target) v[0] = left;
//
//        left = 0, right = n;
//        while (left < right)
//        {
//            int mid = left + (right - left + 1) / 2;
//            if (nums[mid] <= target) left = mid;
//            else if (nums[mid] > target) right = mid - 1;
//        }
//        if (nums[left] == target) v[1] = left;
//
//        return v;
//    }
//};
//
//class Solution
//{
//public:
//    int searchInsert(vector<int>& nums, int target)
//    {
//        int left = 0, right = nums.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] < target) left = mid + 1;
//            else if (nums[mid] >= target) right = mid;
//            else return mid;
//        }
//        if (target > nums[left]) return left + 1;
//        else return left;
//    }
//};

#include<stack>
#include<vector>

class Solution
{
public:

    int Calc(int x, int y, char ch)
    {
        int ans = 0;
        switch (ch)
        {
        case '+':
            ans = x + y;
            break;
        case '-':
            ans = x - y;
            break;
        case '*':
            ans = x * y;
            break;
        case '/':
            ans = x / y;
            break;
        }
        return ans;
    }

    int evalRPN(vector<string>& tokens)
    {
        stack<int> st;
        int i = 0, n = tokens.size();
        while (i < n)
        {
            if (strcmp(tokens[i].c_str(), "+") &&
                strcmp(tokens[i].c_str(), "-") &&
                strcmp(tokens[i].c_str(), "*") &&
                strcmp(tokens[i].c_str(), "/"))
            {
                int val = stoi(tokens[i]);
                st.push(val);
            }
            else
            {
                int val1 = st.top();
                st.pop();
                int val2 = st.top();
                st.pop();
                int ret = Calc(val2, val1, tokens[i][0]);
                st.push(ret);
            }
            i++;
        }
        return st.top();
    }
};

int main()
{
    vector<string> v = { "10","6","9","3","+","-11","*","/","*","17","+","5","+" };
    Solution().evalRPN(v);
    return 0;
}